using System;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;

public class Distance
{
    const int MTC = 2;
    const int level1 = 3;
    const int level2 = 8;
    const int cachelimit = 400;
    const int maxvalue = ushort.MaxValue;
    public Distance(){}
    static string[] g;
    static int n, index;
    static List<int>[] adjList;
    static List<ushort[]> cache;
    static int[] vs;
    static DateTime startTime, endTime;
    public double[] query(int[] u, int[] v)
    {
        startTime = DateTime.Now;
        double[] ret = new double[u.Length];
        for (int i = 0; i < u.Length; i++)
        {
            int d = int.MaxValue, a = u[i], b = v[i];
            foreach (ushort[] c in cache)
            {
                int dd = c[a] + c[b];
                if (d > dd)
                {
                    d = dd;
                }
            }
            ret[i] = distance(u[i], v[i], d);
        }
        Console.WriteLine("{0}\tdone", DateTime.Now - startTime);

        return ret;
    }
    public int process(string[] graphs)
    {
        startTime = DateTime.Now;
        endTime = startTime + new TimeSpan(0,0,30);
        n = graphs.Length;
        Thread[] ts = new Thread[MTC-1];
        Distance[] ds = new Distance[MTC];
        for (int i = 0; i < MTC; i++)
        {
            ds[i] = new Distance(i);
        }
        g = graphs;

//begin
        Console.WriteLine("{0}\tbegin", DateTime.Now - startTime);
        adjList = new List<int>[n];
        cache = new List<ushort[]>();
        vs = new int[n];
        table = new byte[n];
//init
        Console.WriteLine("{0}\tinit...", DateTime.Now - startTime);
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i] = new Thread(new ThreadStart(ds[i].init));
            ts[i].Start();
        }
        ds[MTC - 1].init();
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i].Join();
        }

//init g
        Console.WriteLine("{0}\tinit g...", DateTime.Now - startTime);
        index = -1;
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i] = new Thread(new ThreadStart(ds[i].initg));
            ts[i].Start();
        }
        ds[MTC - 1].initg();
        for (int i = MTC - 2; i >= 0; i--)
        {
            ts[i].Join();
        }

////run
        //Console.WriteLine("{0}\trun...", DateTime.Now - startTime);
        //for (int i = MTC - 2; i >= 0; i--)
        //{
        //    ts[i] = new Thread(new ThreadStart(ds[i].trun));
        //    ts[i].Start();
        //}
        //DateTime t1;
        //TimeSpan timeSpan = new TimeSpan(0L);
        //for (int i = 0; cache.Count < cachelimit && DateTime.Now + timeSpan + timeSpan < endTime; i++, timeSpan += DateTime.Now - t1, timeSpan = new TimeSpan(timeSpan.Ticks / i))
        //{
        //    if (i < 3)
        //        Console.Write("{0}\tmain run...", DateTime.Now - startTime);
        //    t1 = DateTime.Now;
        //    ds[MTC - 1].run();
        //    if (i < 3)
        //        Console.WriteLine("{0} done", DateTime.Now - t1);
        //}
        //valid = false;
        //for (int i = MTC - 2; i >= 0; i--)
        //{
        //    ts[i].Join();
        //}
        //Console.WriteLine("{0}\tall run done...", DateTime.Now - startTime);
        //Console.WriteLine("{0}\tcache...", cache.Count);

        //int[] levels = new int[ushort.MaxValue + 1];
        //foreach (ushort[] c in cache)
        //{
        //    for (int i = 0; i < n; i++)
        //    {
        //        levels[c[i]]++;
        //    }
        //}
        //for (int i = 0; i < 20; i++)
        //{
        //    Console.Write("{0} ", levels[i]);
        //}
        //Console.WriteLine();
        //Console.WriteLine("{0}\tall done...", DateTime.Now - startTime);
        return 0;
    }

    private Distance(int id)
    {
        this.id = id;
        start = id * n / MTC;
        end = (id + 1) * n / MTC;
    }

    private int id, start, end;
    private void init()
    {
        for (int i = start; i < end; i++)
        {
            adjList[i] = new List<int>(50);
        }
    }
    private void initg()
    {
        int i;
        while ((i = Interlocked.Increment(ref index)) < n)
        {
            List<int> list = adjList[i];
            foreach (string s in g[i].Split(' '))
            {
                int a = int.Parse(s);
                if(a != i)
                {
                    lock (list)
                    {
                        list.Add(a);
                    }
                    list = adjList[a];
                    lock (list)
                    {
                        list.Add(i);
                    }
                }
            }
        }
    }
    List<int> q1 = new List<int>(), q2 = new List<int>(), q3 = new List<int>();
    byte[] table;
    Random r = new Random();
    static bool valid;
    private void trun()
    {
        while(valid && cache.Count<cachelimit)
        {
            run();
        }
    }
    const int oLimit = 100000;
    private int distance(int u, int v)
    {
        if(u == v)
        {
            return 0;
        }
        int ul = 0, vl = 0;
        Array.Clear(table, 0, n);
        q1.Clear();
        q2.Clear();
        q1.Add(u);
        q2.Add(v);
        table[u] = 1;
        table[v] = 2;
        List<int> qt; 
        int count = 0;
        for(;;)
        {
            ul++;
            q3.Clear();
            foreach (int a in q1)
            {
                foreach(int aa in adjList[a])
                {
                    if (count++>=oLimit)
                    {
                        return -1;
                    }
                    switch(table[aa])
                    {
                        case 0:
                            q3.Add(aa);
                            table[aa] = 1;
                            break;
                        case 2:
                            return ul + vl;
                    }
                }
            }
            qt = q3;
            q3 = q1;
            q1 = qt;

            vl++;
            q3.Clear();
            foreach(int a in q2)
            {
                foreach (int aa in adjList[a])
                {
                    if (count++ >= oLimit)
                    {
                        return -1;
                    }
                    switch (table[aa])
                    {
                        case 0:
                            q3.Add(aa);
                            table[aa] = 2;
                            break;
                        case 1:
                            return ul + vl;
                    }
                }
            }
            qt = q3;
            q3 = q2;
            q2 = qt;
        }
    }
    private void run()
    {
        List<int> q3;
        double best = double.MaxValue;
        int besti = 0;
        for(int i=0; i<n; i++)
        {
            double d = vs[i] + r.NextDouble();
            if(best > d)
            {
                best = d;
                besti = i;
            }
        }
        ushort v = 0, m = ushort.MaxValue;
        ushort[] list = new ushort[n];
        list[besti] = ushort.MaxValue;
        q1.Clear();
        q1.Add(besti);
        do
        {
            v++;
            q2.Clear();
            if (v <= level1)
            {
                foreach (int a in q1)
                {
                    Interlocked.Increment(ref vs[a]);
                    Interlocked.Increment(ref vs[a]);
                }
            } 
            else if(v<=level2)
            {
                foreach (int a in q1)
                {
                    Interlocked.Increment(ref vs[a]);
                    Interlocked.Increment(ref vs[a]);
                }
            }
            foreach (int a in q1)
            {
                foreach (int b in adjList[a])
                {
                    if (list[b] == 0)
                    {
                        list[b] = v;
                        q2.Add(b);
                    }
                }
            }
            q3 = q2;
            q2 = q1;
            q1 = q3;
        }
        while (q1.Count > 0);
        list[besti] = 0;
        lock(cache)
        {
            cache.Add(list);
        }
    }
}

